package leetcode_二分查找;

/**
 * @author yzh
 * @date 2021/4/7 8:48
 * 搜索旋转排序数组
 * 因为数组是有序的且无重复的
 * 所以翻转之后，位于中间的元素 nums[mid] 一定落在其中一个有序区间中
 * 注意：nums[mid] 不一定是最大值或最小值 7 1 2 3 4 5 6
 * 中间值与最左边的数比较
 * 如果 nums[mid] >= nums[lo]
 *  target >= nums[lo] && target < nums[mid] hi = mid - 1
 * nums[mid] < nums[lo]
 *  target > nums[mid] && target < nums[hi] lo = mid + 1
 *  总之就是哪个部分是有序的，最好就是往哪边走
 *
 *  leetcode_day/_202104/_07_81
 */
public class _33 {
    public static void main(String[] args) {
        System.out.println(4 >> 1);
    }

    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (target == nums[mid]) return mid;
            if (nums[mid] >= nums[low]) {
                if (target < nums[mid] && target >= nums[low]) high = mid - 1;
                else low = mid + 1;
            } else {
                if (target > nums[mid] && target <= nums[high]) low = mid + 1;
                else high = mid - 1;
            }
        }
        return -1;
    }
}
